# coding: utf-8
import pickle
from random import shuffle


def copy(target):
    return pickle.loads(pickle.dumps(target))


class CitySequence:
    def __init__(self):
        self.tour = None  # a sequence of cities
        self.cost = None  # the cost of the tour
        
    def init_solution(self, cities, distance, depot=None, style='random'):
        """ This method will generate an initial solution of high quality.
        @param cities: city set
        @param distance: distance matrix
        @param depot: depot city
        @param style: the style of initial solution
        @return: a solution initiated with random shuffle and optimal insertion
        """
        self.tour = copy(cities)
        depot = cities[0] if depot is None else depot
        if style == 'random':
            shuffle(self.tour)
        elif style == 'greedy':
            self.tour = [depot, depot]
            self.cost = 0
            V = copy(cities)
            V.remove(depot)
            for city in V:
                self.optimal_insert(city, distance)
        self.cost = self.calc_cost(distance)
        return self
    
    def __repr__(self):
        return f'tour:({self.tour}, cost: {self.cost})'
    
    def optimal_insert(self, city, distance, execute=True):
        """
        @param city: [int] the city to be inserted
        @param distance: [float][float] the distance matrix
        @param execute: [bool] whether performs insertion in place
        @return: solution or optimal insertion cost
        """
        assert self.tour and self.cost is not None
        expenses = [distance[self.tour[i - 1]][city]  # add edge (a,b)
                    + distance[city][self.tour[i]]  # add edge (b,c)
                    - distance[self.tour[i - 1]][self.tour[i]]  # remove edge (a,b)
                    for i in range(1, len(self.tour))]
        idx = expenses.index(min(expenses))
        if execute:
            self.tour.insert(idx + 1, city)
            self.cost += expenses[idx]
            return self
        else:
            return expenses[idx]
        
    def calc_cost(self, distance):
        return sum([distance[self.tour[i - 1]][self.tour[i]] for i in range(1, len(self.tour))])\
            + distance[self.tour[-1]][self.tour[0]]
